/**
 * 改进，添加一个list, map用于记录每个元素在list中的位置
 */
export var RandomizedSet = function () {
  this.dict = new Map()
  this.list = []
}

/**
 * @param {number} val
 * @return {boolean}
 */
RandomizedSet.prototype.insert = function (val) {
  if (this.dict.has(val)) return false
  this.list.push(val)
  this.dict.set(val, this.list.length - 1)
  return true
}

/**
 * @param {number} val
 * @return {boolean}
 */
RandomizedSet.prototype.remove = function (val) {
  if (!this.dict.has(val)) {
    return false
  }
  // 从dict中删除，也要把val从list中删除
  const index = this.dict.get(val)
  const last = this.list.length - 1
  const lastVal = this.list[last]
  this.list[index] = lastVal //把最后一个元素放到val的位置
  this.dict.set(lastVal, index) //更新原来在list最后一个元素换位后的位置
  this.list.pop()
  this.dict.delete(val)
  return true
}

/**
 * @return {number}
 */
RandomizedSet.prototype.getRandom = function () {
  const index = Math.floor(Math.random() * this.list.length)
  console.log(this.list, this.dict, index)
  return this.list[index]
}

/**
 * Your RandomizedSet object will be instantiated and called as such:
 * var obj = new RandomizedSet()
 * var param_1 = obj.insert(val)
 * var param_2 = obj.remove(val)
 * var param_3 = obj.getRandom()
 */
